#include <algorithm>
#include <bits/stdc++.h>
#include <climits>
using namespace std;

//单调队列

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> que;
        vector<int> ans;
        if(nums.size() < k){
            for(int i=0; i<nums.size(); ++i){
                while(!que.empty() && que.back()<nums[i]) que.pop_back();
                que.push_back(nums[i]);
            }
            ans.push_back(que.front());
            return ans;
        }
        for(int i=0; i<k; ++i){
            while(!que.empty() && que.back()<nums[i]) que.pop_back();
            que.push_back(nums[i]);
        }
        ans.push_back(que.front());
        for(int i=0; i<nums.size()-k; ++i){
            if(!que.empty() && que.front() == nums[i]) que.pop_front();
            while(!que.empty() && que.back()<nums[i+k]) que.pop_back();
            que.push_back(nums[i+k]);
            ans.push_back(que.front());
        }
        return ans;
    }
};
int main(){
    Solution solution;
    vector<int> nums = {-7,-8,7,5,7,1,6,0};
    solution.maxSlidingWindow(nums, 4);
    return 0;
}